0565. 数组嵌套【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 原地标记

1. 📝 题目描述

• leetcode

索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。

假设选择索引为 i 的元素 A[i] 为 S 的第一个元素，S 的下一个元素应该是 A[A[i]]，之后是 A[A[A[i]]]... 以此类推，不断添加直到 S 出现重复的元素。

示例 1：

输入: A = [5,4,0,3,1,6,2]
输出: 4
解释:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

其中一种最长的 S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

---

提示：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] < nums.length
• A中不含有重复的元素。

2. 🎯 s.1 - 原地标记

c

int arrayNesting(int* nums, int numsSize) {
    int res = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == -1) continue;
        int count = 0, j = i;
        while (nums[j] != -1) {
            int next = nums[j];
            nums[j] = -1;
            j = next;
            count++;
        }
        if (count > res) res = count;
    }
    return res;
}

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var arrayNesting = function (nums) {
  let res = 0
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === -1) continue
    let count = 0,
      j = i
    while (nums[j] !== -1) {
      const next = nums[j]
      nums[j] = -1
      j = next
      count++
    }
    res = Math.max(res, count)
  }
  return res
}

py

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        res = 0
        for i in range(len(nums)):
            if nums[i] == -1:
                continue
            count, j = 0, i
            while nums[j] != -1:
                nxt = nums[j]
                nums[j] = -1
                j = nxt
                count += 1
            res = max(res, count)
        return res

• 时间复杂度：$O(n)$，其中 n 是数组长度
• 空间复杂度：$O(1)$

算法思路：

• 数组是 0~n-1 的排列，形成若干环
• 遍历每个索引，沿着链走并将访问过的元素标记为 -1，记录环长度
• 已标记的元素跳过，每个元素只访问一次